package com.coder.algorithm.offer_2;

import java.util.Arrays;
import java.util.Locale;
import java.util.Stack;

/**
 * 栈的压入、弹出序列
 *
 * @author yuhushuan
 * @date 2020/6/21 01:30
 */
public class _31_1_StackPushPopOrder {

    private static boolean isPopOrder(int[] push, int[] pop) {
        if (push == null || pop == null) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();

        int pushIndex = 0;
        int popIndex = 0;
        while (pushIndex < push.length) {
            // 入栈
            stack.push(push[pushIndex]);
            pushIndex++;

            // 如果出栈数字与栈顶元素一致，则为出栈操作
            while (popIndex < pop.length && pop[popIndex] == stack.peek()) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        print(new int[]{1, 2, 3, 4, 5}, new int[]{4, 5, 3, 2, 1});
        print(new int[]{1, 2, 3, 4, 5}, new int[]{4, 3, 5, 2, 1});
        print(new int[]{1, 2, 3, 4, 5}, new int[]{4, 3, 5, 1, 2});
        print(new int[]{1, 2, 3, 4, 5}, new int[]{4});
        print(new int[]{1, 2}, new int[]{1});
        print(null, null);
        print(new int[]{1, 2}, null);
    }

    private static void print(int[] push, int[] pop) {
        System.out.println(String.format(Locale.getDefault(),
                "入栈序列：%s\n出栈序列：%s\n判断为：%b\n",
                Arrays.toString(push), Arrays.toString(pop), isPopOrder(push, pop)));
    }
}
